home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 4: GNU Archives / Linux Cubed Series 4 - GNU Archives.iso / gnu / glibc-1.09 / glibc-1 / glibc-1.09.1 / stdlib / msort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-18  |  2.5 KB  |  104 lines
  1. /* msort -- an alternative to qsort, with an identical interface.
  2.    Copyright (C) 1992 Free Software Foundation, Inc.
  3.    Written by Mike Haertel, September 1988.
  4.  
  5. This file is part of the GNU C Library.
  6.  
  7. The GNU C Library is free software; you can redistribute it and/or
  8. modify it under the terms of the GNU Library General Public License as
  9. published by the Free Software Foundation; either version 2 of the
  10. License, or (at your option) any later version.
  11.  
  12. The GNU C Library is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15. Library General Public License for more details.
  16.  
  17. You should have received a copy of the GNU Library General Public
  18. License along with the GNU C Library; see the file COPYING.LIB.  If
  19. not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  20. Cambridge, MA 02139, USA.  */
  21.  
  22. #include <ansidecl.h>
  23. #include <stdlib.h>
  24. #include <string.h>
  25.  
  26. #define MEMCPY(dst, src, s)            \
  27.   ((s) == sizeof (int)                \
  28.    ? (*(int *) (dst) = *(int *) (src), (dst))    \
  29.    : memcpy (dst, src, s))
  30.  
  31. static void
  32. DEFUN(msort_with_tmp, (b, n, s, cmp, t),
  33.       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp AND char *t)
  34. {
  35.   char *tmp;
  36.   char *b1, *b2;
  37.   size_t n1, n2;
  38.  
  39.   if (n <= 1)
  40.     return;
  41.  
  42.   n1 = n / 2;
  43.   n2 = n - n1;
  44.   b1 = b;
  45.   b2 = (char *) b + (n1 * s);
  46.  
  47.   msort_with_tmp (b1, n1, s, cmp, t);
  48.   msort_with_tmp (b2, n2, s, cmp, t);
  49.  
  50.   tmp = t;
  51.  
  52.   while (n1 > 0 && n2 > 0)
  53.     {
  54.       if ((*cmp) (b1, b2) <= 0)
  55.     {
  56.       MEMCPY (tmp, b1, s);
  57.       b1 += s;
  58.       --n1;
  59.     }
  60.       else
  61.     {
  62.       MEMCPY (tmp, b2, s);
  63.       b2 += s;
  64.       --n2;
  65.     }
  66.       tmp += s;
  67.     }
  68.   if (n1 > 0)
  69.     memcpy (tmp, b1, n1 * s);
  70.   memcpy (b, t, (n - n2) * s);
  71. }
  72.  
  73. void
  74. DEFUN(qsort, (b, n, s, cmp),
  75.       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp)
  76. {
  77.   CONST size_t size = n * s;
  78.  
  79.   if (size < 1024)
  80.     /* The temporary array is small, so put it on the stack.  */
  81.     msort_with_tmp (b, n, s, cmp, __alloca (size));
  82.   else
  83.     {
  84.       /* It's somewhat large, so malloc it.  */
  85.       int save = errno;
  86.       char *tmp = malloc (size);
  87.       if (tmp == NULL)
  88.     {
  89.       /* Couldn't get space, so use the slower algorithm
  90.          that doesn't need a temporary array.  */
  91.       extern void EXFUN(_quicksort, (PTR __base,
  92.                      size_t __nmemb, size_t __size,
  93.                      __compar_fn_t __compar));
  94.       _quicksort (b, n, s, cmp);
  95.     }
  96.       else
  97.     {
  98.       msort_with_tmp (b, n, s, cmp, tmp);
  99.       free (tmp);
  100.     }
  101.       errno = save;
  102.     }
  103. }
  104.